home *** CD-ROM | disk | FTP | other *** search
/ The CICA Windows Explosion! / The CICA Windows Explosion! - Disc 2.iso / programr / atre27.exe / ATREE_27 / INCLUDE / BV.C < prev    next >
C/C++ Source or Header  |  1992-08-01  |  18KB  |  504 lines
  1. /*****************************************************************************
  2.  ****                                                                     ****
  3.  **** bv.c  for Windows                                                   ****
  4.  ****                                                                     ****
  5.  **** atree release 2.7                                                   ****
  6.  **** Copyright (C) A. Dwelly, R. Manderscheid, M. Thomas, W.W. Armstrong ****
  7.  ****               1991, 1992                                            ****
  8.  ****                                                                     ****
  9.  **** License:                                                            ****
  10.  **** A royalty-free license is granted for the use of this software for  ****
  11.  **** NON_COMMERCIAL PURPOSES ONLY. The software may be copied and/or     ****
  12.  **** modified provided this notice appears in its entirety and unchanged ****
  13.  **** in all derived source programs.  Persons modifying the code are     ****
  14.  **** requested to state the date, the changes made and who made them     ****
  15.  **** in the modification history.                                        ****
  16.  ****                                                                     ****
  17.  **** Patent License:                                                     ****
  18.  **** The use of a digital circuit which transmits a signal indicating    ****
  19.  **** heuristic responsibility is protected by U. S. Patent 3,934,231     ****
  20.  **** and others assigned to Dendronic Decisions Limited of Edmonton,     ****
  21.  **** W. W. Armstrong, President.  A royalty-free license is granted      ****
  22.  **** by the company to use this patent for NON_COMMERCIAL PURPOSES ONLY  ****
  23.  **** to adapt logic trees using this program and its modifications.      ****
  24.  ****                                                                     ****
  25.  **** Limited Warranty:                                                   ****
  26.  **** This software is provided "as is" without warranty of any kind,     ****
  27.  **** either expressed or implied, including, but not limited to, the     ****
  28.  **** implied warrantees of merchantability and fitness for a particular  ****
  29.  **** purpose.  The entire risk as to the quality and performance of the  ****
  30.  **** program is with the user.  Neither the authors, nor the             ****
  31.  **** University of Alberta, its officers, agents, servants or employees  ****
  32.  **** shall be liable or responsible in any way for any damage to         ****
  33.  **** property or direct personal or consequential injury of any nature   ****
  34.  **** whatsoever that may be suffered or sustained by any licensee, user  ****
  35.  **** or any other party as a consequence of the use or disposition of    ****
  36.  **** this software.                                                      ****
  37.  ****                                                                     ****
  38.  **** Modification history:                                               ****
  39.  ****                                                                     ****
  40.  **** 90.05.09 Initial implementation, A.Dwelly                           ****
  41.  **** 91.07.15 Release 2, Rolf Manderscheid                               ****
  42.  **** 92.27.02 Release 2.5 Monroe Thomas                                  ****
  43.  **** 92.03.07 Release 2.6, Monroe Thomas                                 ****
  44.  **** 92.01.08 Release 2.7, Monroe Thomas                                 ****
  45.  ****                                                                     ****
  46.  *****************************************************************************/
  47.  
  48. /*****************************************************************************
  49.  ****                                                                     ****
  50.  **** Include Files                                                       ****
  51.  ****                                                                     ****
  52.  *****************************************************************************/
  53.  
  54. #ifndef __WINDOWS_H
  55. #include <windows.h>
  56. #endif
  57.  
  58. #ifndef __STDIO_H
  59. #include <stdio.h>
  60. #endif
  61.  
  62. #ifndef __STDLIB_H
  63. #include <stdlib.h>
  64. #endif
  65.  
  66. #ifndef __ASSERT_H
  67. #include <assert.h>
  68. #endif
  69.  
  70. #ifndef __ALLOC_H
  71. #include <alloc.h>
  72. #endif
  73.  
  74. #ifndef __BV_H
  75. #include "bv.h"
  76. #endif
  77.  
  78. /* Public and private procedures */
  79.  
  80. #define public
  81. #define private static
  82.  
  83. /* Memory check */
  84.  
  85. #define MEMCHECK(p) \
  86.         if (p == NULL){ \
  87.                          MessageBox(NULL,"Could not allocate requested memory",\
  88.                          "bv",MB_OK | MB_ICONSTOP);\
  89.                          PostQuitMessage(0);\
  90.                          exit(0);\
  91.                         }
  92.  
  93. #define BYTE    8 /* Byte size in bits.*/
  94.  
  95. /*
  96.  * Types
  97.  */
  98.  
  99. typedef int bool_t;      /*
  100.                           * Only TRUE, FALSE, UNEVALUATED or ERROR
  101.                           * are used in these variables
  102.                           */
  103.  
  104. /*****************************************************************************
  105.  ****                                                                     ****
  106.  **** LPBIT_VEC bv_create(length)                                         ****
  107.  ****                                                                     ****
  108.  **** int length;                                                         ****
  109.  ****                                                                     ****
  110.  **** Synopsis:                                                           ****
  111.  ****                                                                     ****
  112.  **** Produces a vector of _length_ bits, each one of which has been set  ****
  113.  **** to 0                                                                ****
  114.  *****************************************************************************/
  115.  
  116.  
  117. public LPBIT_VEC FAR PASCAL
  118. bv_create(length)
  119.  
  120. int length;
  121.  
  122. {
  123.     int i;
  124.     LPBIT_VEC out_vec;
  125.  
  126.     assert(length > 0);
  127.  
  128.     out_vec = (LPBIT_VEC) farmalloc((unsigned)sizeof(bit_vec));
  129.     MEMCHECK(out_vec);
  130.  
  131.     out_vec -> len = length;
  132.     out_vec -> bv = farmalloc((unsigned) (length + BYTE - 1) / BYTE);
  133.     MEMCHECK(out_vec -> bv);
  134.  
  135.     for (i = 0; i < (length + BYTE - 1) / BYTE; i++)
  136.     {
  137.         *((out_vec -> bv) + i) = (char) 0;
  138.     }
  139.  
  140.     return(out_vec);
  141. }
  142.  
  143. /*****************************************************************************
  144.  ****                                                                     ****
  145.  **** LPBIT_VEC bv_pack(unpacked,length)                                  ****
  146.  ****                                                                     ****
  147.  **** LPSTR unpacked;                                                     ****
  148.  **** int length;                                                         ****
  149.  ****                                                                     ****
  150.  **** This routine takes an array _arr_ of zero and one characters        ****
  151.  **** and returns a packed bit vector suitable for use with the other     ****
  152.  **** routines in this library.                                           ****
  153.  *****************************************************************************/
  154.  
  155. public LPBIT_VEC FAR PASCAL
  156. bv_pack(unpacked,length)
  157.  
  158. LPSTR unpacked;
  159. int length;
  160.  
  161. {
  162.     LPBIT_VEC out_vec;
  163.     LPSTR out_ptr;
  164.     int i;
  165.     int j;
  166.     int bitptr;
  167.  
  168.     /* Create the structure */
  169.  
  170.     out_vec = (LPBIT_VEC) farmalloc((unsigned)sizeof(bit_vec));
  171.     MEMCHECK(out_vec);
  172.  
  173.     out_vec -> len = length;
  174.     out_vec -> bv = farmalloc((unsigned) (length + BYTE - 1) / BYTE);
  175.     MEMCHECK(out_vec -> bv);
  176.  
  177.     /* Pack the vector */
  178.  
  179.     out_ptr = out_vec -> bv;
  180.  
  181.     bitptr = 0;
  182.     for (i = 0; i < (length + BYTE - 1) / BYTE; i++)
  183.     {
  184.         *out_ptr = 0;
  185.  
  186.         for (j = 0; j < BYTE; j++)
  187.         {
  188.             if (bitptr < length)
  189.             {
  190.                *out_ptr |= (unpacked[bitptr] << j);
  191.                bitptr++;
  192.             }
  193.             else
  194.             {
  195.                 break;
  196.             }
  197.         }
  198.         out_ptr++;
  199.     }
  200.  
  201.     /* Return the vector */
  202.  
  203.     return(out_vec);
  204. }
  205.  
  206. /*****************************************************************************
  207.  ****                                                                     ****
  208.  **** int bv_diff(v1,v2)                                                  ****
  209.  ****                                                                     ****
  210.  **** LPBIT_VEC v1;                                                       ****
  211.  **** LPBIT_VEC v2;                                                       ****
  212.  ****                                                                     ****
  213.  **** This function returns the number of bits that are unequal in the    ****
  214.  **** two vectors. They must be the same number of bits in each vector    ****
  215.  *****************************************************************************/
  216.  
  217. public int FAR PASCAL
  218. bv_diff(v1,v2)
  219.  
  220. LPBIT_VEC v1;
  221. LPBIT_VEC v2;
  222. {
  223.     int diff = 0;
  224.     int i;
  225.  
  226.     assert (v1 -> len == v2 -> len);
  227.     for (i = 0; i < v1 -> len; i++)
  228.     {
  229.         if (bv_extract(i,v1) != bv_extract(i,v2))
  230.         {
  231.             diff++;
  232.         }
  233.     }
  234.  
  235.     return(diff);
  236. }
  237.  
  238. /*****************************************************************************
  239.  ****                                                                     ****
  240.  **** LPBIT_VEC bv_concat(n,vectors)                                      ****
  241.  ****                                                                     ****
  242.  **** int n;                                                              ****
  243.  **** LPBIT_VEC *vectors;                                                 ****
  244.  ****                                                                     ****
  245.  **** Synopsis:                                                           ****
  246.  ****                                                                     ****
  247.  **** Returns the bit vector which is the string concatenation of each    ****
  248.  **** bit vector in _vector_; _n_ is the number of elements in _vector_.  ****
  249.  *****************************************************************************/
  250.  
  251. public LPBIT_VEC FAR PASCAL
  252. bv_concat(n,vector)
  253.  
  254. int n;
  255. LPBIT_VEC FAR *vector;
  256.  
  257. {
  258.     int size;
  259.     LPBIT_VEC out_vec;
  260.     LPSTR str;
  261.     int i;
  262.     int j;
  263.     int count;
  264.  
  265.     /* Work out how big the new vector will be */
  266.  
  267.     size = 0;
  268.     for (i = 0; i < n; i++)
  269.     {
  270.         size += vector[i] -> len;
  271.     }
  272.  
  273.     /* Unpack the input vectors */
  274.  
  275.     str = farmalloc((unsigned) size);
  276.     MEMCHECK(str);
  277.  
  278.     count = 0;
  279.     for (i = 0; i < n; i++)
  280.     {
  281.         for (j = 0; j < vector[i] -> len; j++)
  282.         {
  283.             str[count] = bv_extract(j,vector[i]);
  284.             count++;
  285.         }
  286.     }
  287.  
  288.     out_vec = bv_pack(str,size);
  289.  
  290.     farfree(str);
  291.  
  292.     return(out_vec);
  293. }
  294.  
  295. /*****************************************************************************
  296.  ****                                                                     ****
  297.  **** LPBIT_VEC bv_copy(vector)                                           ****
  298.  ****                                                                     ****
  299.  **** LPBIT_VEC vector;                                                   ****
  300.  ****                                                                     ****
  301.  **** Synopsis:                                                           ****
  302.  ****                                                                     ****
  303.  **** Returns a copy of the bit vector _vector_.                          ****
  304.  *****************************************************************************/
  305.  
  306. public LPBIT_VEC FAR PASCAL
  307. bv_copy(vector)
  308.  
  309. LPBIT_VEC vector;
  310. {
  311.     LPBIT_VEC out_vec;
  312.     int i;
  313.  
  314.     /* Work out how big the new vector will be */
  315.  
  316.     out_vec = (LPBIT_VEC) farmalloc((unsigned) sizeof(bit_vec));
  317.     MEMCHECK(out_vec);
  318.  
  319.     out_vec -> len = vector -> len;
  320.     out_vec -> bv = farmalloc((unsigned) (vector -> len + BYTE - 1) / BYTE);
  321.     MEMCHECK(out_vec -> bv);
  322.  
  323.     for (i = 0; i < (vector -> len + BYTE - 1) / BYTE; i++)
  324.     {
  325.         out_vec -> bv[i] = vector -> bv[i];
  326.     }
  327.  
  328.     return(out_vec);
  329. }
  330.  
  331. /*****************************************************************************
  332.  ****                                                                     ****
  333.  **** void bv_set(n,vec,bit)                                              ****
  334.  ****                                                                     ****
  335.  **** int n;                                                              ****
  336.  **** LPBIT_VEC vec;                                                      ****
  337.  **** BOOL bit;                                                           ****
  338.  ****                                                                     ****
  339.  **** Synopsis:                                                           ****
  340.  ****                                                                     ****
  341.  **** Sets bit _n_ in _vec_ to have the value in _bit_.                   ****
  342.  *****************************************************************************/
  343.  
  344. public void FAR PASCAL
  345. bv_set(n,vec,bit)
  346.  
  347. int n;
  348. LPBIT_VEC vec;
  349. BOOL bit;
  350.  
  351. {
  352.     char mask;
  353.     LPSTR b;
  354.     assert(n < vec -> len);
  355.  
  356.     mask = 0x1;
  357.     b = (vec -> bv) + ((int) (n / BYTE));
  358.  
  359.     if (bit)
  360.     {
  361.         *b |= (mask << (n % BYTE));
  362.     }
  363.     else
  364.     {
  365.         *b &= ~(mask << (n % BYTE));
  366.     }
  367. }
  368.  
  369. /*****************************************************************************
  370.  ****                                                                     ****
  371.  **** BOOL bv_extract(n,vec)                                              ****
  372.  ****                                                                     ****
  373.  **** int n;                                                              ****
  374.  **** LPBIT_VEC vec;                                                      ****
  375.  ****                                                                     ****
  376.  **** Synopsis:                                                           ****
  377.  ****                                                                     ****
  378.  **** Returns the _n_th bit of _vec_.                                     ****
  379.  *****************************************************************************/
  380.  
  381. public BOOL FAR PASCAL
  382. bv_extract(n,vec)
  383.  
  384. int n;
  385. LPBIT_VEC vec;
  386.  
  387. {
  388.     register int mask = 0x1;
  389.  
  390.     assert(n < vec -> len);
  391.     return(((*((vec -> bv) + ((int) (n / BYTE)))) & (mask << (n % BYTE))) != 0);
  392. }
  393.  
  394. /*****************************************************************************
  395.  ****                                                                     ****
  396.  **** int bv_print(stream, vector)                                        ****
  397.  ****                                                                     ****
  398.  **** FILE *vector;                                                       ****
  399.  **** LPBIT_VEC vector;                                                   ****
  400.  ****                                                                     ****
  401.  **** Synopsis:                                                           ****
  402.  ****                                                                     ****
  403.  **** Prints out _vector_ in binary, MSB is the rightmost.                ****
  404.  **** Returns 0 for success, 1 on failure.                                ****
  405.  *****************************************************************************/
  406.  
  407. public int FAR PASCAL
  408. bv_print(stream, vector)
  409.  
  410. FILE *stream;
  411. LPBIT_VEC vector;
  412.  
  413. {
  414.     LPSTR ptr; /* Points to the current char */
  415.     char mask;
  416.     int bits; /* Counts the number of bits output */
  417.     int  i;
  418.  
  419.     bits = 0;
  420.     for (ptr = vector -> bv; bits < vector -> len; ptr++)
  421.  
  422.     {
  423.         mask = 0x1;
  424.         for (i = 0; i < BYTE; i++)
  425.         {
  426.             if (fprintf(stream, (*ptr & mask) ? "1" : "0") == EOF)
  427.             {
  428.                 return(1);
  429.             }
  430.             bits++;
  431.             if (bits == vector -> len)
  432.             {
  433.                 break;
  434.             }
  435.             mask <<= 1;
  436.         }
  437.     }
  438.     return(0);
  439. }
  440.  
  441. /*****************************************************************************
  442.  ****                                                                     ****
  443.  **** void bv_free(vector)                                                ****
  444.  ****                                                                     ****
  445.  **** LPBIT_VEC vector;                                                   ****
  446.  ****                                                                     ****
  447.  **** Synopsis:                                                           ****
  448.  ****                                                                     ****
  449.  **** Frees the memory used by _vector_                                   ****
  450.  *****************************************************************************/
  451.  
  452. public void FAR PASCAL
  453. bv_free(vector)
  454.  
  455. LPBIT_VEC vector;
  456.  
  457. {
  458.     farfree(vector -> bv);
  459.     farfree(vector);
  460. }
  461.  
  462. /*****************************************************************************
  463.  ****                                                                     ****
  464.  **** BOOL bv_equal(v1,v2)                                                ****
  465.  ****                                                                     ****
  466.  **** LPBIT_VEC v1;                                                       ****
  467.  **** LPBIT_VEC v2;                                                       ****
  468.  ****                                                                     ****
  469.  **** Synopsis:                                                           ****
  470.  ****                                                                     ****
  471.  **** Returns TRUE if each bit in v1 and v2 have the same value in the    ****
  472.  **** same position. It returns FALSE otherwise.                          ****
  473.  *****************************************************************************/
  474.  
  475. public BOOL FAR PASCAL
  476. bv_equal(v1,v2)
  477.  
  478. LPBIT_VEC v1;
  479. LPBIT_VEC v2;
  480.  
  481. {
  482.     bool_t eq;
  483.     int i;
  484.  
  485.     eq = TRUE;
  486.  
  487.     if (v1 -> len != v2 -> len)
  488.     {
  489.         eq = FALSE;
  490.     }
  491.     else
  492.     {
  493.         for (i = 0; i < (v1 -> len + BYTE - 1) / BYTE; i++)
  494.         {
  495.             if (v1 -> bv[i] != v2 -> bv[i])
  496.             {
  497.                 eq = FALSE;
  498.                 break;
  499.             }
  500.         }
  501.     }
  502.  
  503.     return(eq);
  504. }